暑期班汇总

2025暑期班

把所有的内容全部汇总到同一篇文章中,便于查找。

2025年6月30日 扫描线与Arrangement

CGAL中的2DArrangement算法

输入输出

输入:

1
一组 x‑单调曲线(X_monotone_curve_2)和/或点(Point_2),它们位于一个二维参数域(如平面或曲面)上 。

输出:

1
一个 二维细分(arrangement),即由这些曲线/点引起的细胞划分,包括顶点、边(由曲线段表示)和面,整体储存在一个 DCEL(双连通边列表)数据结构中 。

其解决了什么问题

这个模块解决了在平面或曲面上由多条(可能相交的)x‑单调曲线构建精确细分的问题,支持:

  • 增量插入:可以逐条插入曲线(insert / insert_non_intersecting_curve),自动处理交点、重叠、拆分等 。

  • 处理交叉与重叠:需要模型 ArrangementXMonotoneTraits_2,支持交点计算、曲线分解与合并 。

  • 输入输出格式化:支持读写 arrangement 至/自流(ArrangementInputFormatter / OutputFormatter) 。

广泛应用于计算几何——如构建 Voronoi 图、布尔运算、Minkowski 和球面几何等 。

2025年7月1日 微分几何-曲线

曲线的切向量

1
2
3
4
对一条参数曲线:
γ(t) = (x(t),y(t)) 或 γ(t) = (x(t),y(t),z(t))
切向量定义为该曲线在参数𝑡下的导数:
T(t) = (γ'(t)) = (dx/dt, dy/dt) 或 (dx/dt, dy/dt, dz/dt)

其几何意义为:表示点沿着曲线运动时的瞬时方向

单位切向量与弧长参数化

单位切向量定义为切向量的单位化形式:
$$
T(t)=\gamma^{\prime}(t)=\left(\frac{dx}{dt},\frac{dy}{dt}\right)\quad\text{或}\quad\left(\frac{dx}{dt},\frac{dy}{dt},\frac{dz}{dt}\right)
$$
弧长参数化是指重新用”沿曲线的真实长度s”作为参数的曲线表示形式,其满足:
$$
|| \frac{d\gamma}{ds}|| = 1
$$

即在任意s处,单位切向量恒为单位长度。

曲率

曲率描述的是曲线在某点弯曲的成都,直觉上即为”拐的有多厉害”。

  • 对于平面曲线,曲率定义为单位切向量关于弧长的变化率:
    $\kappa(s)=\left|\frac{d\hat{T}}{ds}\right|$

  • 对于任意参数t,则有:

  • $\kappa(t)=\frac{|\gamma^{\prime}(t)\times\gamma^{\prime\prime}(t)|}{|\gamma^{\prime}(t)|^3}\quad\mathrm{(3D)},\quad\kappa(t)=\frac{|x^{\prime}y^{\prime\prime}-y^{\prime}x^{\prime\prime}|}{(x^{\prime\prime}2+y^{\prime\prime}2)^{3/2}}\quad\mathrm{(2D)}$

直线:$k = 0$

圆:$k = 1/R$

法向量与曲率向量

  • 法向量$N(t)$ : 垂直于单位切向量的方向,指向曲线”弯曲的那一侧”。

  • 曲率向量$k(t)$ : 曲率与法向量的乘积

$$
\vec{k}(t) = k(t) · N(t)
$$

几何意义:

  • 法向量给出了”朝内”的方向

  • 曲率法向量综合表达了弯曲程度+弯曲方向

2025年7月2日 微分几何-曲面

曲面的表示方法

1:参数化形式
$$
X(u,v) = (x(u,v),y(u,v),z(u,v))
$$

  • 支持从二维区域映射到三维空间

2:隐式表示
$$
f(x,y,z) = 0
$$

  • 用于重建、隐函数建模(SDF)

3:显式表示
$$
z=f(x,y)
$$

  • 表达能力弱,仅可用于特定局部场景

混合积 (Mixed Product)

给定三个三维向量$a,b,c$,它们的混合积定义为:

$$
[a,b,c] = a·(b×c)
$$
几何意义:

1
混合积表示的是由三维向量a,b,c构成的平行六面体的有向体积
  • 若混合积>0:右手系,体积为正
  • 若混合积<0:左手系,体积为负
  • 若混合积=0:三向量共面,体积为0

无向体积:$V = |[a,b,c]|$

使用场景:判断三向量是否共面

共变导数 (Covariant Derivative)

为了解决一个根本问题:

1
在弯曲空间或曲面上,怎么“正确地”比较两个不同点处的向量?

基本定义

设 $M$ 是一个曲面或流形,$\vec{X}$ 是一个向量场,$\vec{V} \in T_pM$ 是某点处的切向量,则:

$\nabla_{\vec{V}}\vec{X}$

表示:在方向 $\vec{V}$ 上,向量场 $\vec{X}$ 的变化率,结果仍在切空间 $T_pM$ 内部。

它是一种“修正过的导数”,避免了将向量导出曲面的错误。

计算过程

令 $x^1, x^2, \dots, x^n$ 是局部坐标系

设向量场:
$$
\vec{X} = X^i \frac{\partial}{\partial x^i}
$$
共变导数公式:
$$
\nabla_j X^i = \frac{\partial X^i}{\partial x^j} + \Gamma^i_{jk} X^k
$$
其中:

  • $\Gamma^i_{jk}$ 是 Christoffel 符号(联络系数),反映了坐标轴自身的“弯曲”。

  • Christoffel 符号的计算

    若给定度量 $g_{ij}$(即第一基本形式),则 Christoffel 符号通过如下公式计算:
    $$
    \Gamma^i_{jk} = \frac{1}{2} g^{im} \left( \frac{\partial g_{mj}}{\partial x^k} + \frac{\partial g_{mk}}{\partial x^j} - \frac{\partial g_{jk}}{\partial x^m} \right)
    $$
    其中 $g^{im}$ 是 $g_{ij}$ 的逆矩阵。

在测地线方程中的应用

测地线要求:
$$
\nabla_{\dot{\gamma}} \dot{\gamma} = 0
$$
也就是说,速度向量场在自身方向上的共变导数为零

展开成坐标形式:
$$
\ddot{x}^i + \Gamma^i_{jk} \dot{x}^j \dot{x}^k = 0
\quad \text{for all } i = 1, 2, \dots, n
$$
这就是测地线方程的局部表达式

2025年7月3日 网格曲面的基本结构-拉普拉斯算子

拉普拉斯算子

在连续情况下,拉普拉斯算子是:
$$
\Delta u = \nabla \cdot \nabla u
$$
而在网格曲面上(离散几何处理),它通常使用cotangent Laplacian表示为:
$$
\Delta u_i = \frac{1}{2A_i} \sum_{j\in N(i)}(cot\alpha_{ij}+cot\beta_{ij})(u_j-u_i)
$$
其中:

  • $u_i$是顶点上的函数值,如温度、高程、颜色等
  • $A_i$是顶点面积权重,如Voronoi面积或1/3面积
  • $\alpha,\beta$是相邻三角形对该边的对角

拉普拉斯方程:$\Delta u = 0$

定义:无源稳态的扩散问题(调和函数)

几何 / 物理意义:

  • 系统已经达到稳定状态,没有任何源项
  • 函数值在局部邻域内的加权平均等于自身 -> “无弯曲方向”
  • 等价于极小化函数在曲面上的Dirichlet能量

曲面网格上的应用:

  • 利用$\Delta u = 0$消除高频扰动,用于Mesh Fairing / 平滑
  • 利用调和映射保持角度结构,用于UV参数化

泊松方程:$\Delta u = f$

定义:有源稳态扩散项,源项$f$指定了空间中函数变化的“原因”

几何 / 物理意义:

  • 系统稳定但内部有源项,如热源,电荷,外力等

  • 拉普拉斯方程的推广,可用最小能量原理表示为:
    $$
    \underset{u}{min}\int_M||\nabla u||^2 - 2fu
    $$

网格曲面上的应用:

  • 利用点云->法向->源项$f$这一思路重建表面,即泊松表面重建
  • 利用源图像梯度作为$f$,实现图像融合
  • 基于法线散度生成泊松源项,求解SDF

无源热方程:$\frac{\partial u}{\partial t} = \Delta u$

定义:描述随时间演化的扩散过程(如热传导、污染扩散)

几何 / 物理意义:

  • 初始函数$u(x,0)$经过拉普拉斯控制的平滑演化;
  • 模型具有“高频信息快速衰减”的特性;
  • 时间越长越趋于均匀分布。

网格曲面上的应用:

  • 利用热扩散定义的点的局部特征实现Heat Kernel Signature
  • 利用热扩散+归一化梯度场反推测地线估计距离

振动模态方程:$\frac{\partial^2 u}{\partial t^2} = \Delta u$

也写作$\Delta \phi = -\lambda \phi$ (特征值问题)

定义:描述物体随时间的自然振动,如鼓面、琴弦等。

几何 / 物理意义:

  • 在曲面上传播的波动现象;
  • 不同频率的特征函数$\phi_i$,表示不同的振动模式;
  • 常用于找出“物体最自然的变形方向”。

网格曲面上的应用:

  • 利用拉普拉斯特征函数变形共振模式以实现模态分析
  • 利用特征值作为全局shape descriptor实现形状检索
  • 利用振动模态构成模拟基础来实现物理仿真

2025年7月4日 渲染

最实用的渲染工具:blender-toolbox

感觉,没什么好说的

2025年7月5日 网格曲面的提取

M/arching Cubes(MC)

核心思想:在规则的三维体素网格上,对每个小立方体判断其八个顶点是否在等值面内,通过256种拓扑配置之一,查表生成三角面片。

优点:简单高效,适合GPU实现

缺点:可能产生拓扑不一致,难以处理尖锐边缘

Marching Tetrahedra(MT)

核心思想:将一个立方体划分为多个四面体,在每个四面体中进行线性插值并构造三角面片

优点:避免MC的拓扑不一致问题

缺点:结果比MC更细碎,可能有更多三角形

Dual Contouring(DC)

核心思想:不直接生成三角片,而是计算每个体素的等值面交点,生成“dual vertex”(一般在体素内部,通过 QEF 求解最佳点),再连接这些点生成面片。

优点:保留锐利特征(如边角),输出结构更紧凑

缺点:实现复杂,依赖高质量的梯度信息

Dual Marching Cubes(DMC)

  • 核心思想:结合 MC 和 DC 的优势,构建 dual 网格但沿用 marching cubes 的遍历框架
  • 优点:支持细节表达,适合处理复杂结构,拓扑更好
  • 缺点:实现较复杂,算法细节多,较难调试

FlexiCubes

核心思想:一种拓扑可控的等值面提取方法,自动在规则网格中选择适当的网格单元分辨率(adaptive cells),使得重建的网格可以更好地保留特征和拓扑结构。

优点:支持高质量拓扑结构(如避免小孔或错误连接),可扩展性强

缺点:实现更复杂,需要预处理

Reach for the Spheres(RFTS)

  • 核心思想:使用球体(spheres)而非体素作为构建块来提取等值面,避免了传统方法中的笛卡尔栅格偏置。使用一组球进行空间覆盖,再利用球的交叠关系推导网格。
  • 优点:表面更平滑,避免体素栅格导致的锯齿状误差,更好地处理稀疏或低分辨率数据
  • 缺点:依赖较复杂的数据结构(球体之间的邻接),运行较慢

Reach for the Arcs(RFTA)

核心思想:扩展 RFTS 方法,用弧(而不是直线)来连接球体之间的连接点,从而进一步提升拟合精度,特别是在曲面上。

优点:重建结果更加平滑,精度更高,能更自然地表达曲面变化

缺点:计算更复杂,需要处理圆弧几何

Power Diagram Method

核心思想:一种基于加权点集的空间划分方法,Power Diagram 是 Voronoi 图的推广。每个点有一个“权重”,影响它的作用区域。

在网格重建中的应用:可用于构建 implicit surface,特别是 Poisson reconstruction 的空间划分。在 Dual Contouring 的拓展中也有应用,用于构建更稳定的 dual 网格结构。

优点:可以更好地控制细分区域和权重分布,几何表达能力强

缺点:构建成本较高,数值精度要求高

2025年7月6日 符号距离场及三维重构

隐式曲面 - 符号距离场

有符号距离场基本定义:

定义一个标量场:
$$
f:\mathbb{R}^3\to\mathbb{R}
$$
当值小于零时,该点在表面外,当值小于零时,该点位于表面内,表面即为提取零值面:
$$
{x:f(x)=0}
$$
优点:

  • 可以表达任意形状,任意亏格
  • 将形状编码为一个函数,可以使用MLP表达
  • 方便判断内外、查询距离
  • 隐式CSG(Constructive Solid Geometry:构造实体几何)
  • 它与曲率有深刻的关联

隐式重建与显式曲面重建的对比:

隐式曲面重建:保流形和光滑形

显式曲面重建:保特征

2025年7月7日 无监督深度学习的四边形网格重建

背景

无监督四边形网格重建主要目的是从点云、网格、深度图、或隐式场等输入中,直接输出结构良好的四边形网格(quad mesh),不依赖显式的 ground-truth quad mesh supervision。常使用几何正则、重建误差、边界对齐等自监督损失。

特点

  • 无需标注数据(如 ground-truth quad mesh)

  • 强调几何约束:如对齐、光滑性、四边形一致性、面角平衡等

  • 常与参数化(parameterization)结合

常见方法/流程

  • 隐式字段学习(Implicit Field):通过神经网络拟合输入几何的隐式表示(如 SDF),之后重建四边形网格。
  • UV parameterization 学习:将输入模型映射为 2D 平面上规则的四边形图案。
  • 四边化优化:在无监督损失下,对神经表示或参数化结果进行优化得到良好四边形划分。

代表性工作

NeurCross: A Neural Approach to Computing Cross Fields for Quad Mesh Generation

QuadriFlow: A Scalable and Robust Method for Quadrangulation(不是深度学习,但常用于比较)

Neural-Singular-Hessian: Implicit Neural Representation of Unoriented Point Clouds by Enforcing Singular Hessian

Aligning Gradient and Hessian for Neural Signed Distance Function

2025年7月8日 有监督深度学习的三维重建

背景

此类方法依赖训练集提供的 ground-truth 四边形网格,训练神经网络直接回归或预测目标网格。

特点

  • 精度高,但依赖标注数据
  • 常用于从图像或深度图生成四边形网格
  • 任务多样化:如图像到网格、扫描数据拟合、手工建模辅助

常见方法/流程

  • 图像 → 四边形网格:输入 RGB 图片,预测结构化的四边形网格(如用于人脸/衣物等)。
  • 深度图 → 四边形网格:结合几何先验,学习从深度图恢复高质量 quad mesh。
  • Mesh Refinement:以初始 mesh 为基础,学习对其优化为四边结构。

代表性工作

Laplacian2Mesh: Laplacian-Based Mesh Understanding

2025年7月10日 测地线

等距不变性:

同一个模型,不同的姿势,两个定点之间的测地线距离不会发生变化

梯度 : $\nabla f = (\frac{\partial f}{\partial x_1},\frac{\partial f}{\partial x_2},…,\frac{\partial f}{\partial x_n})$

Input : scalar function $f:\mathbb{R}^n\to\mathbb{R}$

Output : vector field : $\nabla f:\mathbb{R}^n \to \mathbb{R}$

散度 : $divV = \frac{\partial V_x}{\partial x}+\frac{\partial V_y}{\partial y}$

Input : vector field : $V:\mathbb{R}^2 \to \mathbb{R}^2$

Output : scalar function : $divV : \mathbb{R}^2 \to \mathbb{R}$

Laplacian : $\nabla f = div\nabla f = \sum^{3}_{i=1}\frac{\partial f}{\partial x^2_i}$

Input : vector field : $f:\mathbb{R}^n \to \mathbb{R}$

Output : scalar field : $\nabla f:\mathbb{R}^n \to \mathbb{R}$

nbala$\nabla$算子反应的并非本身函数的性质,而是定义域本身的性质,即可以反应曲面本身的性质

网格上的函数

顶点上的值赋值 : $f(x_i) = f_i$
三角形内部的线性插值 : $f(x) = f_iB_i(x) + f_jB_j(x) + f_kB_k(x)$

梯度:
$$
分片线性插值的梯度公式 : \nabla f(x) = f_i\nabla B_i(x) + f_j\nabla B_j(x) + f_k\nabla B_k(x)
= \frac{f_i}{2A_T}(x_k-x_j)^\bot + \frac{f_j}{2A_T}(x_i-x_k)^\bot + \frac{f_k}{2A_T}(x_j-x_i)^\bot
$$

最陡上升方向 $\nabla B_i(x) = \nabla B_i = \frac{(x_k - x_j)^\bot}{2A_T}$

向量场中的散度

一个向量场在三角形内部是分片连续的;
$$
散度定理 : \int_U divV = \int_{\partial U}V.n
$$
即:一个区域内的散度积分等于其边界上的通量。
$$
离散散度表达式:div(V)iA(i) = \sum{ijk}V_{ijk}(xj-xk)^\bot
$$
顶点面积 : $A(i) = \frac{1}{3}\sum_{i\in T}A_T$

即:顶点 $i$ 的面积等于其关联三角形面积的 $\frac{1}{3}$ 加权和。

网格上的拉普拉斯算子

$$
梯度在三角形 $\triangle(x_i, x_j, x_k)$ 内的表达式:(\nabla f){ijk} = \frac{f_i}{2A{ijk}}(x_k-x_j)^\bot + \frac{f_j}{2A_{ijk}}(x_i-x_k)^\bot + \frac{f_k}{2A_{ijk}}(x_j-x_i)^\bot
$$

是每个顶点函数值与对边法向量的线性组合。
$$
拉普拉斯离散形式:(Lf)iA(i) = \sum{ijk}(\nabla f){ijk}.(x_j-x_k)^\bot = \sum{ij}\frac{1}{2}(cot\alpha_{ij}+cos\beta_{ij})(f_i-f_j)
$$
其中 $\alpha_{ij}, \beta_{ij}$ 是边 $(i, j)$ 对应的两个角。

**性质: 如果 $f$ 是常函数,则: : $Lf = 0$ 。**即常函数的拉普拉斯为零。

拉普拉斯矩阵 $L$ 的大小为 $n \times n$,其中 $n$ 是顶点个数。
$$
矩阵系数定义:L_{ij}A(j) = \frac{1}{2}cot(\alpha) + \frac{1}{2}cot(\beta)
$$
矩阵形式(带质量矩阵 $A$): : $AL = -W$
$$
其中 W 是权重矩阵,定义为:W_{ij} =
\left{
\begin{aligned}
\frac{1}{2}(cot(\alpha)+cot{\beta}),if:i ~ j\
-\sum_j W_{ij}, if:i=j\
0, otherwise
\end{aligned}
\right.
$$

$$
质量矩阵 A(Mass Matrix):A_{ij} =
\left{
\begin{aligned}
A(j),if:i = j\
0,otherwise
\end{aligned}
\right.
$$

曲面上的热传导方程

给定一个紧致曲面(compact surface),热传导方程为 : $\frac{\partial f}{\partial t} = \nabla f$

时间离散化:$\frac{f_{t+1}-f_t}{dt} = \nabla f_{t+1}$

空间离散化 : $\frac{f_{t+1}-f_t}{dt} = -A^{-1}Wf_{t+1}$

重排得到的线性系统(求解 $f_{t+1}$):$(A+dtW)f_{t+1} = Af_t$
$$
热核定义:k_t(x,y):\mathbb{R}^+\times M \times M \to \mathbb{R}
$$
它表示在时间$t$内,从点$x$传递到点$y$的热量。
$$
热扩散公式:f(x,t) =\int_M k_t(x,y)f(y,0)dy
$$
表示初始热分布$f(y,0)$在时间$t$后在点$x$的热量。
$$
谱展开形式:k_t(x,y) = \sum_iexp(-t\lambda_i)\phi_i(x)\phi_i(y)
$$
其中:

  • $\lambda_i,\phi_i$ 表示拉普拉斯算子的特征值和特征函数;
  • 在网格上可用离散拉普拉斯算子的本征对进行数值计算。

离散热核

$$
在网格上,热核可以表示为一个矩阵:k_t = \sum_i exp(-t\lambda_i)\phi_i\phi_i^\bot
$$

其中:

  • $\phi_i$是拉普拉斯矩阵的本征向量(长度为顶点数的列向量)
  • $k_t$是一个$n\times n$的对称矩阵($n$为顶点数)
  • $k_t(x,y)$表示从$x$到$y$的热传递量

离散热扩散公式

$$
给定初始热分布f_0,经过时间t后热量分布为:f_t = \sum_i exp(-t\lambda_i)\phi_i\phi_i^\bot Af_0
$$

$$
或用谱展开记忆形式表示:f_0 = \sum_i\phi_i(\phi_i^\bot Af_0)
$$

其中$A$是质量矩阵(常为对角矩阵,表示每个顶点的面积)。

热核签名

$$
定义:HKS(x) = k_t(x,x) = \sum_i exp(-t\lambda_i)\phi_i(x)^2
$$

物理意义:

表示在时间$t$后**仍保留在点$x$**的热量。

性质:

  • 对不同时间梯度$t$的HKS,可以反应局部到整体的几何特征;
  • 常用于形状分析、特征点检测、形状匹配等任务。

波核签名

用于衡量某个点在不同频率能量下的响应程度,可以看作是量子力学粒子在形状上驻留的概率分布
$$
对每个点x和能量水平e,定义为:WKS(x,e) = \sum_{i=0}^{N}exp(-\frac{(e-log\lambda_i)^2}{2\delta^2})\phi_i(x)^2
$$
其中:

  • $\lambda_i$:离散拉普拉斯算子的第$i$个特征值;
  • $\phi_i(x)$:第$i$个特征函数在点$x$的取值;
  • $e$:频率(能量)采样点,通常在$log\lambda$空间中等间距选取;
  • $\delta$:带宽控制参数,决定每个频率的范围;
  • $N$:使用的特征值/特征函数数量

2025年7月11日 空间划分结构

KD-Tree

基本概念

KD-Tree 是一种二叉树结构,用于在 k 维空间中对点集进行递归划分。每个节点表示一个超平面划分,该超平面与某一维的坐标轴对齐。

构建方式

  1. 给定一组 k 维点。
  2. 初始从根节点开始,选择一个维度(如 x 轴)作为划分维度。
  3. 找到该维度的中位数作为划分点,构建平面将空间分为左右两个子空间。
  4. 对两个子空间递归进行相同操作,每层轮换划分维度。

应用场景

  • 点云搜索(最近邻/范围查询)
  • 光线追踪(早期)
  • 机器学习(KNN 分类器)
  • 地图构建、碰撞检测

特点

  • 对静态点集效果良好
  • 不适合频繁插入和删除
  • 适合低维数据(2D~10D)

Octree(八叉树)

基本概念

Octree 是一种递归八叉划分结构,用于在 3D 空间中对场景/体素/点云进行管理。每个节点将空间分为 8 个等体积的子空间。

构建方式

  1. 从整个空间开始作为根节点。
  2. 若当前节点中包含的点/物体数量大于阈值:
    • 则将该节点划分为 8 个子立方体,并递归构建。
  3. 若子块为空则可不存储,形成稀疏结构。

应用场景

  • 3D 游戏碰撞检测
  • 点云压缩与表示(如 PCL)
  • 体绘制(volume rendering)
  • 地图建模(SLAM)

特点

  • 结构紧凑,适合稀疏3D数据
  • 动态更新比 KD-Tree 更方便
  • 空间局部性强,适合体素类操作

BSP(Binary Space Partitioning)

基本概念

BSP 是一种基于任意平面划分的二叉空间结构,最早用于2D/3D场景中快速可见性计算绘制顺序排序

构建方式

  1. 选择一个物体面片作为划分平面。
  2. 用该平面将场景划分为前后两部分:
    • 在该面前的物体放入“前子树”
    • 在该面后的物体放入“后子树”
    • 相交的要进行裁剪或特殊处理
  3. 递归对每个子空间执行相同划分。

应用场景

  • 经典 FPS 游戏(如《DOOM》)
  • 可见性计算(从某一点看有哪些物体)
  • 渲染排序(Painter’s algorithm)

特点

  • 可以使用任意方向平面(比 KD-Tree 更灵活)
  • 适合静态场景;动态场景构建代价高
  • 可用于处理非轴对齐几何体(如不规则墙面)

BVH(Bounding Volume Hierarchy)

基本概念

BVH 是一种用于快速相交检测的层次包围体结构,常用于光线追踪、碰撞检测等。每个节点代表一个包围体(如 AABB、OBB、球体等),其子节点代表更小的子物体或子包围体。

构建方式

  1. 对所有物体构建包围盒(如 AABB)。
  2. 将它们划分为两个子集合,使得两个集合的包围盒重叠最小(如用中轴或 SAH 面积启发式)。
  3. 递归构建左右子树,每个节点保存当前包围体信息。

应用场景

  • 光线追踪(ray tracing)
  • 碰撞检测
  • GPU 渲染加速

特点

  • 动态更新成本比 KD-Tree 小
  • 对复杂物体结构更友好
  • 使用启发式可提高构建质量(如 SAH)

扩展文章 : Curve Complexity Heuristic KD-trees for Neighborhood-based Exploration of 3D Curves

2025年7月19日 优化

核心问题:我们通常需要解决一个无约束优化问题:

$minimize\ F(x)$

其中$x\in R^n$是我们要优化的目标向量(如顶点位置、相机参数、光照系数等),$F(x) : R^n -> R$ 是我们想要最小化的目标函数(如变形能量、渲染误差、物理势能等)。

牛顿法(Newton’s Method)

  • 核心思想: 利用目标函数 $F(x)$ 在当前点 $x_k$ 处的局部二次泰勒展开来近似该函数,然后直接找到这个二次近似函数的最小值点作为下一个迭代点 $x_{k+1}$。它需要用到目标函数的一阶导数(梯度 $g_k = \nabla F(x_k)$)和二阶导数(Hessian矩阵 $H_k = \nabla ^2F(x_k)$)。
  • 推导 (直观理解):
    1. 泰勒展开: 在点 $x_k$ 附近,$F(x)$ 近似为:
      $F(x_k + d) ≈ F(x_k) + g_k^T * d + (1/2) * d^T * H_k * d$
      其中 d 是搜索方向(从 $x_k$ 出发的位移向量)。
    2. 最小化二次模型: 为了找到使这个二次近似函数最小的 $d$,我们对其关于 $d$ 求导并令导数为零:
      $\nabla _d [ … ] = g_k + H_k * d = 0$
    3. 牛顿方程: 得到线性方程组:
      $H_k * d = -g_k$
    4. 迭代更新: 解这个线性方程组得到搜索方向 $d_k$,然后更新参数:
      $x_{k+1} = x_k + d_k$

BFGS (Broyden–Fletcher–Goldfarb–Shanno)

  • 核心思想: BFGS 是最著名、最成功的拟牛顿法 (Quasi-Newton Method) 之一。它不需要显式计算 Hessian 矩阵 $H_k$。取而代之的是,它通过利用当前梯度和上一步的梯度信息,构造一个 Hessian 矩阵的逆 $B_k$(或其近似 $H_k^{-1}$)的近似矩阵。BFGS 直接维护并更新对 $H_k^{-1}$ 的近似 $B_k$。

  • 关键特性:

    • 避免显式 Hessian: 最大的优势是无需计算昂贵的 Hessian,只需计算目标函数的梯度 $g_k$。

    • 近似二阶信息: 通过分析连续迭代点处的梯度和位移变化 $(s_k = x_{k+1} - x_k, y_k = g_{k+1} - g_k)$,BFGS 巧妙地更新 $B_k$ 以满足割线条件 $B_{k+1} * y_k = s_k$。这个条件要求近似的 Hessian 逆在方向 $s_k$ 上的作用效果应与真实的 Hessian 逆一致(至少能正确预测梯度变化 $y_k$)。

    • 收敛速度: 虽然不如牛顿法快,但在适当的条件下(如 Wolfe 线搜索)通常具有超线性收敛速度(介于线性收敛和二次收敛之间),比仅用一阶梯度的方法(如梯度下降)快得多。

    • 保持正定性: BFGS 更新公式设计得当初始 $B_0$ 正定且满足曲率条件 $s_k^T y_k > 0$(通常由 Wolfe 线搜索保证)时,可以保证 $B_k$ 始终保持正定。这确保了搜索方向 $d_k = -B_k * g_k$ 总是下降方向。

    • 存储要求: 需要存储一个稠密的 $n \times n$ 矩阵 $B_k$。这对于大规模问题($n$ 非常大)可能成为瓶颈($O(n²)$ 存储)。针对此问题,有 L-BFGS (Limited-memory BFGS) 变种。

L-BFGS:

  • 解决存储问题: L-BFGS 是 BFGS 为处理大规模优化问题而设计的变体。它不存储完整的 $n \times n$ 近似矩阵 $B_k$。

  • 工作原理: 它只存储最近 $m$(通常 $m$ 很小,如 $5-20$)步的位移向量 $s_k$ 和梯度变化向量 $y_k$。利用这些向量,L-BFGS 在需要计算搜索方向 $d_k = -B_k * g_k$ 时,通过一个巧妙的递归公式,仅使用 $g_k$ 和存储的 ${s_i, y_i}$ 序列$(i = k-m, …, k-1)$来隐式地计算出 $B_k * g_k$ 的结果(即 $-d_k$),而无需显式构造 $B_k$。

  • 优势: 存储需求从 $O(n²)$ 显著降低到 $O(m*n)$,使其能够高效处理参数维度 $n$ 高达数百万甚至更大的问题。收敛速度通常接近完整的 BFGS。

梯度下降法 (Gradient Descent) 及其变种:

  • 基本思想: 沿着当前点负梯度方向 (d_k = -g_k) 进行搜索,找到使函数值下降的点。是最简单的一阶方法。
  • 变种:
    • 最速下降法 (Steepest Descent): 一种特定的梯度下降,但在图形学中术语常混用。
    • 动量法 (Momentum): 在更新方向中加入上一步更新的惯性,帮助加速收敛并减少震荡(如穿越狭窄山谷)。
    • Nesterov 加速梯度 (NAG): Momentum 的改进版,提供更好的理论收敛性质。
    • AdaGrad/RMSProp/Adam: 自适应学习率算法。Adam (Adaptive Moment Estimation) 是目前极其流行且鲁棒的一阶优化器,它结合了动量(一阶矩估计)和自适应学习率(二阶矩估计),对超参数(尤其是学习率)不太敏感,在训练深度学习模型中几乎成为标配,在图形学中涉及深度学习的任务(如神经渲染、生成模型)也广泛应用。

2025年7月20日 分片光滑结构的几何表示

  • 核心问题:表示具有不连续特征(如折痕、边界)的连续曲面,常见于CAD建模和几何处理。

  • 核心思想:
    将复杂曲面分解为多个光滑曲面片(patches),在相邻面片连接处施加连续性约束($C^0$, $C^1$, $G^1$ 等),同时允许特定位置存在不连续性。

  • 关键方法:

样条表示:NURBS/T-Splines 通过控制点和节点向量定义光滑曲面片,边界处通过节点重复实现连续性控制

细分曲面:Catmull-Clark/Loop 细分规则在极限曲面产生 $C^1$/ $C^2$ 连续,通过特殊规则处理特征边(如尖锐折痕)

基于网格的方法

  • 显式标记特征边(crease edges)

  • 在非特征区域使用双拉普拉斯平滑

  • 特征边界处采用局部参数化重组

  • 混合表示:结合隐式函数(RBF)和显式网格处理复杂拓扑

2025年7月21日 三维点云的法向一致性相关

核心问题:为无结构点云估计一致朝向的法向量,避免重建曲面时出现孔洞或自交。

  • 核心思想:利用局部几何结构和全局传播机制,使相邻点法向共轭(即指向曲面同侧)。
  • 关键技术
    1. 局部估计
      • PCA 法:对 $k$-NN 邻域协方差矩阵最小特征向量
      • 加权最小二乘平面拟合
    2. 全局一致化
      • 最小生成树(MST)传播:从种子点开始沿最近邻图传播方向
      • 基于视线约束:利用扫描视角信息($\mathbf{n} \cdot (\mathbf{c}-\mathbf{p}) > 0$)
      • 图割优化:构建能量函数 $E=\sum_{(i,j)} \mathbf{n}_i \cdot \mathbf{n}_j - \lambda \mathbf{n}_i \cdot (\mathbf{p}_j-\mathbf{p}_i)$
    3. 深度学习方法
      • PCPNet 等网络直接预测一致法向
      • 通过法向-位置联合损失函数增强一致性

2025年7月22日 基元检测

核心问题:从点云/网格中自动检测基本几何形状(平面、圆柱、球体等)。

  • 核心思想:将复杂几何体分解为简单几何基元(Primitives)的组合。
  • 主流方法
    • 传统方法
      • RANSAC:随机采样拟合基元,通过内点数量验证假设
      • Hough 变换:将点映射到参数空间累积投票
      • 区域生长:基于法向/曲率相似性聚类
    • 深度学习方法
      • SPFN:端到端预测基元类型和参数
      • 基于图神经网络的分割+拟合
    • 混合方法
      • 先通过深度学习粗分割,再用最小二乘精确拟合
      • 基元间关系建模(如正交性约束)

2025年7月23日 AIGC基本原理

核心问题:利用AI生成符合人类需求的视觉/几何内容。

  • 核心思想:学习数据分布并采样生成新样本,实现”从描述到内容”的转化。

  • 关键组件

    • 文本编码器(如CLIP)
    • 去噪网络(U-Net架构)
    • 调节机制(Classifier-free Guidance)

2025年7月24日 Offset

核心问题:构建与原始几何体保持恒定距离的新曲面。

  • 数学定义

    Soffset={p±d⋅n(p)∣p∈S}Soffset={p±dn(p)∣pS}

    其中 $d$ 为偏移距离,$\mathbf{n}$ 为单位法向。

  • 技术挑战

    • 自交处理
      • 距离场裁剪($d < 1/\kappa_{max}$)
      • 拓扑修复(MAT 引导)
    • 特征保持
      • 尖角处圆弧过渡
      • 曲率自适应偏移
    • 高效计算
      • GPU 并行距离场生成
      • 层次化 AABB 树检测碰撞

2025年7月25日 中轴

核心问题:提取形状的拓扑骨架和尺寸信息。

  • 核心定义:最大内切球的圆心集合,满足:

    MA(Ω)={x∈Ω∣∃p1,p2∈∂Ω,∥x−p1∥=∥x−p2∥=rmax(x)}M**A(Ω)={x∈Ω∣∃p1,p2∈∂Ω,∥xp1∥=∥xp2∥=rmax(x)}

  • 计算方法

    方法 原理 优点 缺点
    Voronoi法 计算边界点Voronoi图取内部边 理论完备 噪声敏感
    距离场法 提取距离场脊线 抗噪性好 计算昂贵
    收缩法 几何驱动收缩 保留特征 需迭代优化
  • 应用场景

    • 网格简化(QEM 基于中轴)
    • 动画骨骼生成
    • 增材制造支撑结构优化

2025年7月26日 AIGC更多应用

核心领域:计算机图形学中的创新应用

  • 3D内容生成
    • 文本→3D:DreamFusion(SDS损失)、Point-E
    • 图像→3D:PIFuHD(隐式函数)
    • 生成式CAD:AutoCAD SketchGraph
  • 材质与光照
    • 神经辐射场(NeRF)材质解耦
    • 基于物理的材质生成(DiffMat)
  • 动画合成
    • 运动风格迁移(VAE+GAN)
    • 面部表情生成(3DMM+Diffusion)
  • 场景生成
    • ProcTHOR:程序化室内场景
    • Gaia:开放世界地形生成

2025年7月26日 3DGS的基本原理

核心问题:实现实时的神经辐射场渲染。

  • 关键技术
    1. 椭球投影
      Σ′=JWΣWTJTΣ′=J**WΣWTJ**T
      其中 $J$ 为投影雅可比,$W$ 为视角矩阵
    2. 自适应控制
      • 梯度监控:$|\nabla \mathcal{L}|$ 过大时分裂高斯
      • 尺度监控:$\max(\sigma) > \theta$ 时克隆高斯

2025年7月27日 3DGS

优化与扩展:提升3DGS的实用性和表现力

  • 训练加速技术

    • 层次化初始化:从SfM点云构建初始高斯

    • 损失函数

      L=(1−λ)∥I^−I∥1+λD-SSIM(I^,I)L=(1−λ)∥I^−I∥1+λD-SSIM(I^,I)

    • CUDA优化:并行排序(Radix Sort on GPU)

  • 动态场景处理

    • 4D高斯:$ \mu(t) = \mu_0 + \mathbf{v}t $
    • 形变场:MLP预测位移 $\delta \mu = f(\mu, t)$
  • 语义增强

    • 嵌入语义高斯:$\mathbf{s} \in \mathbb{R}^k$ 附加特征向量
    • 应用:交互式编辑、物体分割
  • 局限与突破

    问题 解决方案
    显存消耗 高斯剪枝($\alpha < \tau$)
    透明物体 折射建模(Snell’s Law)
    镜面反射 微表面高斯扩展

每个主题均保持技术深度和结构一致性,符合您要求的格式标准。